#include "stdafx.h"
#include "CppUnitTest.h"

using namespace Microsoft::VisualStudio::CppUnitTestFramework;


namespace NativeTest_Question21
{
	//2.1 Write code to remove duplicates from an unsorted linked list. 
	//FOLLOW UP How would you solve this problem if a temporary buffer is not allowed? 
	typedef struct node{
		int val;
		node* Next;
	} node;

	void RemoveDeuplicated(node* n)
	{
		if(n == NULL) return;

		while(n && n->Next)
		{
			node* walker = n;
			while(walker->Next)
			{
				if(walker->Next->val == n->val)
				{
					walker->Next = walker->Next->Next;
				}
				else
				{
					walker = walker->Next;
				}
			}

			n = n->Next;
		}
	}
}

namespace NativeTest
{
	using namespace NativeTest_Question21;
	TEST_CLASS(Question21)
	{
	public:

		TEST_METHOD(Question21_TestMethod1)
		{
			int n = 10;
			int a[] = {  3, 2, 1, 3, 5, 6, 2, 6, 3, 1};
			node* data, *head;
			
			for (int i = 0; i < n; i++)
			{
				node* tn = new node();
				tn->val= a[i];
				tn->Next = NULL;
				if(i == 0) { head = tn; data = tn;}
				else { data->Next = tn, data = tn;}
			}
			
			data = head;
			for (int i = 0; i < n; i++)
			{
				Assert::AreEqual(a[i], data->val);
				data = data->Next;
			}

			RemoveDeuplicated(head);

			int expected[] = {3, 2, 1, 5, 6};
			int expectedlen = 5;
			data = head;
			for (int i = 0; i < expectedlen; i++)
			{
				Assert::AreEqual(expected[i], data->val);
				data = data->Next;
			}
		}

	};
}